Appendix A, which is part of the present disclosure, is included in a microfiche appendix consisting of 1 sheet of microfiche having a total of 31 frames, and the microfiche appendix is incorporated herein by reference in its entirety. Microfiche Appendix A is a listing of pseudo code for computer programs and related data that can be prepared in the language VERILOG for implementing circuitry including a synchronizer that receives and stores graphics data for the generation of a screen display, for use with one illustrative implementation of this invention as described more completely below.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
A personal computer 10 (FIG. 1A) includes a graphics processor 14 that generates a display of a three-dimensional (abbreviated as xe2x80x9c3Dxe2x80x9d) image on a screen 11 under the control of a central processing unit 15. Graphics processor 14 forms the displayed image from descriptions of one or more graphics primitives, such as a line 16 (FIG. 1B) that connects points xe2x80x9cAxe2x80x9d and xe2x80x9cBxe2x80x9d, a triangle 17 (FIG. 1C) that connects points xe2x80x9cC,xe2x80x9d xe2x80x9cD,xe2x80x9d and xe2x80x9cE,xe2x80x9d a fan 18 (FIG. 1D) and a strip 19 (FIG. 1E).
The image displayed on screen 11 is typically formed by a two-dimensional array of picture elements (called xe2x80x9cpixelsxe2x80x9d) P101-P109 (not all pixels are labeled in FIG. 1F) each of which has one or more attributes (such as color or texture). To reduce the hardware required to process all pixels at once, a screen 11 is subdivided into rectangular areas (called xe2x80x9ctilesxe2x80x9d) T1-TN, and each tile TI contains an equal number of pixels (e.g. 16 pixels) that form a portion of the displayed image. Each tile TI (in this example formed by the sixteen pixels being arranged in a square four pixels tall and four pixels wide) is held and processed one at a time in an on-chip memory included in graphics processor 14.
In such a xe2x80x9ctiledxe2x80x9d architecture, it is necessary to determine the identities of tiles that are covered by one or more graphics primitives (such as triangles 110 and 120 in FIG. 1F) that are to be displayed on screen 11. In the example illustrated in FIG. 1F, triangle 110 has vertices 111-113 and sides 114-116, whereas triangle 120 has vertices 112, 113 and 117, and sides 116, 118 and 119. The touching of a tile TI (wherein 1xe2x89xa6Ixe2x89xa6N) by triangles 110 and 120 is indicated by the presence (or absence) of the triangles"" identifiers in a xe2x80x9cbinxe2x80x9d associated with tile TI, as shown in Table 1 below:
For convenience, not all bins are shown in Table 1. One prior art method (also called xe2x80x9cbrute forcexe2x80x9d method) for the xe2x80x9cbinningxe2x80x9d of triangles (that is performed to obtain Table 1) examines each tile TI (wherein 1xe2x89xa6Ixe2x89xa6N) in screen 11, and checks whether any of triangles 110 and 120 covers tile TI.
Another prior art method (also called xe2x80x9cbounding boxxe2x80x9d method) uses a rectangle (called xe2x80x9cbounding boxxe2x80x9d) that touches the vertices of a triangle to be binned, and identifies all tiles within such a bounding box. For example, a bounding box 121 can be drawn around vertices 111-113 of triangle 110, followed by identification of tiles T2-T4, T8-T10, T14-T16, T20-T22 and T26-T28 that are located within bounding box 121.
The bounding box method results in certain tiles (e.g. tiles T2 and T8) being identified although these tiles are not touched by the triangle being binned (e.g. triangle 110). However, the bounding box method eliminates the need to examine (for triangle 110) tiles that are outside of bounding box 121 (such as tiles T1, T5-T7, T11-T13, T17-T19, T23-T25 and T29-TN). Therefore, the bounding box method is more efficient than the brute force method. Bounding boxes (also called xe2x80x9cextentxe2x80x9d boxes) are described in the book entitled xe2x80x9cComputer Graphics, Principles and Practicexe2x80x9d by Foley, van Dam, Feiner and Hughes, Addison-Wesley Publishing Company, Second Edition in C, 1996 (see pages 660-663; see also pages 336-337).
A circuit (hereinafter xe2x80x9cgeometry tilerxe2x80x9d) in accordance with this invention implements a method described herein to identify one or more tiles (in the form of, e.g. rectangular areas) on a computer""s screen that are covered by (or touched by) a convex polygon (defined to be a polygon wherein each diagonal is fully contained within the polygon, and wherein each diagonal connects two vertices that do not belong to the same line segment of the polygon). Specifically, the geometry tiler identifies tiles (either precisely or approximately) by use of edges of the graphics primitive.
In one embodiment, the geometry tiler identifies the following types of tiles that are covered by or touched by a convex polygon: (a) vertex tiles, (b) edge tiles, and (c) interior tiles. Vertex tiles are tiles that are covered by the vertices of the convex polygon. Edge tiles are tiles that are not at the vertices, and are covered by or touched by line segments that form edges of the convex polygon. Interior tiles are tiles that are not covered by the edges or the vertices of a convex polygon, but are covered by an area enclosed by the convex polygon.
In one implementation, the geometry tiler includes a separate and distinct component for identifying (e.g. by driving on a predetermined bus a signal indicative of the item to be identified) two types of tiles: a vertex tiler that identifies vertex tiles, and a segment scanner that identifies edge tiles. The geometry tiler also includes an interior enumerator that identifies all tiles (including interior tiles, edge tiles and vertex tiles) that are covered by the convex polygon. Note that other implementations of a geometry tiler may have fewer components or more components than described herein. In this implementation, edge tiles along two opposing segments (e.g. a bottom segment and a top segment) of the convex polygon are identified simultaneously, so that all edge tiles are identified when scanning from a left most vertex to a right most vertex is completed.
Identification of edge tiles as described herein eliminates identification of one or more tiles (hereinafter xe2x80x9cuntouchedxe2x80x9d tiles) that are merely located adjacent to a convex polygon, but are not covered or touched by the convex polygon. Specifically, identification of tiles in a precise manner as described herein (e.g. identification of only those tiles that are covered by a to-be-displayed polygon) eliminates the prior art identification of tiles that are neither covered nor touched by the convex polygon.
Elimination of one or more untouched tiles from the identified tiles as described herein reduces both time and storage as follows. Elimination of untouched tiles reduces the time otherwise required in the prior art to identify the tiles to be processed for displaying a primitive, and the time to process the identified tiles for display. Moreover, elimination of one or more untouched tiles from the identified tiles also reduces the number of storage locations otherwise required in the prior art to hold the identities of the tiles to be processed, and the memory bandwidth otherwise required to transfer the tile identities to other circuits.
In one embodiment, a geometry tiler evaluates a function (also called xe2x80x9ctest functionxe2x80x9d) to determine the location of a current tile relative to the convex polygon (specifically, relative to a line segment of the convex polygon). One example of such a test function is the line function F(x,y)=ax+by+c that is based on Cartesian coordinates (x,y) and on the mathematical representation y=mx+n (wherein m=(xe2x88x92a/b) is the slope and n=(xe2x88x92c/b) is the y intercept at x=0 if b is not 0) of a line passing through a segment of the convex polygon. Line function F(x,y) has a value that is equal to zero when a point (x,y) is on the line, and the value is positive on one side of the line and negative on another side of the line. In one implementation, line function F(x,y) is set up (for each line segment of the convex polygon) to have a positive value on a line""s side that contains the interior of the convex polygon.
In another implementation, function F(x,y) is set up for an edge, and values of the function are determined at various corners of a current tile. If the values are positive at all four corners, the current tile is above and to the left of the edge if the slope of the edge is positive and if the interior of the polygon is below the edge. Similarly, if the values are negative at all four corners, the current tile is below and to the right of the edge. If some values of F(x,y) at the four corners of a tile are positive, and other values are negative, the current tile covers the edge (assuming the current tile is a tile between two vertex tiles). One or more of these three tests (of the sign of the line function""s value) are used to identify as edge tiles only those tiles that are covered by the edges of the convex polygon. Thereafter, identification of all tiles that are located between edge tiles yields interior tiles covered by the convex polygon.
In one embodiment, the geometry tiler starts at a vertex of the convex polygon, and identifies as the current tile a tile that contains the vertex. If an edge of the convex polygon extends from the current tile upwards and to the right (as determined from a positive slope m), the sign of the function""s value is positive at all points to the left and above the edge, if the interior of the polygon is above the edge. The sign is negative at all points below and to the right of the edge if the interior of the polygon is below the edge. The function""s sign at the upper right corner of the current tile indicates whether the edge passes through the upper side of the current tile or the right side of the current tile.
A geometry tiler of this embodiment identifies a covered side of a tile by evaluating the function at just one corner of the current tile. In an alternative embodiment, the geometry tiler evaluates the function at each of three corners of the tile (in the example, the upper left, upper right and lower right corners of the tile). The geometry tiler determines the corners of the tile at which the evaluated function has different signs, and identifies the side passing through these corners to be the tile""s side covered by the edge. The edge covers a tile""s side that passes through corners at which the evaluated function has different signs.
In one particular implementation, the function is Fnew=Fold+xcex94y*stepxxe2x88x92xcex94x*stepy, wherein stepx is the distance along the x axis of a new position from an old position, stepy is the distance along the y axis of the new position from the old position, and Fold is a value of the function at the old position, xcex94x is the projection distance of the edge along the x axis and xcex94y is the projection distance of the edge along the y axis. An old position can be, for example, a left most end point of the edge, with Fold set to zero (by definition) at the left most end point.
The just-described implementation eliminates computation of the slope of a segment, and is therefore faster than other implementations (because the just-described implementation does not involve division). Moreover, in one example of this implementation stepx and stepy are both powers of 2 (such as 4, 16, 32 or 64), and the multiplication is accomplished by a shift operation that needs to be performed only once for each edge. So, the geometry tiler of this embodiment evaluates the line function to determine a side (also called xe2x80x9ccovered sidexe2x80x9d) of a current tile through which an edge of a convex polygon passes.
The geometry tiler then selects a tile adjacent to the covered side to be the current tile (i.e. the covered side is common to both tiles). If the selected tile (hereinafter xe2x80x9ccurrent tilexe2x80x9d) is not covered by another end point of the edge, the geometry tiler returns to determining the current tile""s side that is covered by the edge. In this manner, the geometry tiler iteratively moves from one end point of an edge to the other end point, while identifying tiles that are covered by the edge. As noted above, the geometry tiler also iterates between edge tiles covered by two different edges, and identifies all tiles located therebetween as interior tiles.
In one implementation, the geometry tiler performs the following four operations prior to identifying all tiles that are covered by or touched by a convex polygon: (a) determines attributes of the convex polygon (e.g. computes values related to line segments that form the convex polygon), (b) determines iteration descriptors by using the attributes (e.g. sorts vertices of the convex polygon to generate a list that contains vertices ordered along a scanning direction, and identifies xe2x80x9cvertex tilesxe2x80x9d as tiles covered by a vertex), (c) for each segment in the convex polygon, scans the segment and identifies each tile (called xe2x80x9cedge tilexe2x80x9d) that is covered by the segment, and (d) for each column of tiles in the screen, scans from one edge tile in the column to another edge tile in the column and identifies all tiles (including edge tiles) that cover an area enclosed by the segments of the polygon.
As noted above, the geometry tiler of this implementation identifies all the tiles that are covered by a convex polygon. The tiles identified by the just-described geometry tiler do not include a significant number (e.g. up to half the total number in some cases) of tiles that are otherwise identified by the prior art method (such as the bounding box method). The elimination of identification of up to half the number of tiles (in some cases) reduces the prior art time required to process a convex polygon by half. Moreover, elimination of identification of up to half the tiles also reduces by half the number of storage locations otherwise required to hold the identities of tiles to be processed for a convex polygon and reduces by half the memory bandwidth otherwise required to transfer the identities to other circuits.